package 简单多状态问题;

/**
 * @Date 2024/6/5 17:33
 * @description: 力扣740: 删除并获得点数
 * .            https://leetcode.cn/problems/delete-and-earn/description/
 * @Author LittleNight
 */
public class likou740 {

    // 预处理: 因为原数组有可能不连续, 将数组nums中的数统计到arr数组中,然后在数组arr中,做一次打家劫舍1:
    // https://leetcode.cn/problems/house-robber/
    public int deleteAndEarn(int[] nums) {
        // 1.创建dp表
        // 2.初始化
        // 3.填表
        // 4.返回值

        // 题目中nums[i] 最大是10000
        int n = 10001;
        int[] arr = new int[n];
        for(int x : nums) {
            // if(arr[x] == 0) arr[x] = x;
            // else arr[x] += x;
            arr[x] += x;
        }
        // f[i] 表示选择 i 位置的最大点数
        // g[i] 表示不选择 i 位置的最大点数
        int[] f = new int[n];
        int[] g = new int[n];
        f[0] = arr[0]; g[0] = 0;

        // 这里没有下标映射关系
        for (int i = 1; i < n; i++) {
            // 选择 i 位置, 那么前一个肯定不选
            f[i] = g[i - 1] + arr[i];
            // 不选择 i 位置, 那么前一个可以选也可以不选
            g[i] = Math.max(f[i - 1], g[i - 1]);
        }
        // 返回值, 到最后选或者不选, 看一下整体的最大的
        return Math.max(f[n - 1], g[n - 1]);
    }
}
